package _16_设计;

import java.util.HashMap;
import java.util.Map;

// 使用数组节点实现
public class Trie {

    // 字符中只包含小写字母，可以直接使用数组
    private Trie[] children;

    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
    }

    public void insert(String word) {
        int lenStr = word.length();

        Trie cur = this;
        for (int i = 0; i < lenStr; i++) {
            char curChar = word.charAt(i);
            int index = curChar - 'a';
            if (cur.children[index] == null) {
                cur.children[index] = new Trie();
            }
            cur = cur.children[index];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Trie trie = getTrie(word);
        return trie != null && trie.isEnd;
    }

    public boolean startsWith(String prefix) {
        return getTrie(prefix) != null;
    }

    private Trie getTrie(String key) {
        int lenStr = key.length();

        Trie cur = this;
        for (int i = 0; i < lenStr; i++) {
            char curChar = key.charAt(i);
            int index = curChar - 'a';
            if (cur.children[index] == null) {
                return null;
            }
            cur = cur.children[index];
        }
        return cur;
    }

}
